package datastructure.book.dp._2_linear_pre_section.single.all;

import org.junit.jupiter.api.Test;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;

public class _13_Solution {

    @Test
    public void test(){
        int[] arr = {1,2,3,4,5,6,7,8,9,10};
        System.out.println(lenLongestFibSubseq2(arr));
    }
    public int lenLongestFibSubseq(int[] arr) {
        HashSet<Integer> set = new HashSet<>();
        for (int value : arr) {
            set.add(value);
        }
        int max = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i+1; j < arr.length; j++) {
                int pre = arr[j];
                int next = arr[i] + arr[j];
                int tempMax = 2;
                while (set.contains(next)) {
                    tempMax++;
                    int temp = pre;
                    pre = next;
                    next = temp + next;
                }
                if (tempMax > 2 && tempMax > max) {
                    max = tempMax;
                }
            }
        }
        return max;
    }

    public int lenLongestFibSubseq2(int[] arr) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            map.put(arr[i],i);
        }
        int[][] dp = new int[arr.length][arr.length];
        int max = 0;
        for (int i = 1; i < dp.length; i++) {
            for (int j = i+1; j < dp.length; j++) {
                int pre = arr[j] - arr[i];
                if (pre >= arr[i]) {
                    break;
                }
                Integer preIndex = map.get(pre);
                if (preIndex == null) {
                    dp[i][j] = 0;
                } else {
                    dp[i][j] = dp[preIndex][i]+1;
                    max = Math.max(max,dp[i][j]);
                }
            }
        }
        return max > 0 ? max+2 : 0;
    }
}
